Mining frequent closed patterns in pointset databases

In this paper, we proposed an efficient algorithm, called PCP-Miner (Pointset Closed Pattern Miner), for mining frequent closed patterns from a pointset database, where a pointset contains a set of points. Our proposed algorithm consists of two phases. First, we find all frequent patterns of length two in the database. Second, for each pattern found in the first phase, we recursively generate frequent closed patterns by a frequent pattern tree in a depth-first search manner. Since the PCP-Miner does not generate unnecessary candidates, it is more efficient and scalable than the modified Apriori, SASMiner and MaxGeo. The experimental results show that the PCP-Miner algorithm outperforms the comparing algorithms by more than one order of magnitude.     

基于Iceberg概念格的最大频繁项集挖掘

最大频繁项集挖掘算法存在扫描数据集次数多和候选集规模过大等局限。基于Iceberg概念格模型,提出一种在Iceberg概念格上挖掘最大频繁项集的算法ICMFIA。该算法通过一次扫描数据集构建Iceberg概念格,利用Iceberg概念格中频繁概念之间良好的覆盖关系能快速计算出最大频繁项集所对应的最大频繁概念,所有最大频繁概念的内涵就是所求的最大频繁项集的集合。实验结果表明,该算法具有扫描数据集次数少和挖掘效率高的优点。     

基于三元互关联后继树的Web日志挖掘

针对二元的互关联后继树模型进行改进,构造三元互关联后继树,并结合Web日志的特点,构造Web事务集的互关联后继树和增量更新模型,设计基于三元互关联后继树的频繁路径挖掘算法,挖掘Web日志中的频繁路径。通过实验证明了基于三元互关联后继树和改进后的模型的出色插入查询性能。     

Top-down mining of frequent closed patterns from very high dimensional data

Frequent pattern mining is an essential theme in data mining. Existing algorithms usually use a bottom-up search strategy. However, for very high dimensional data, this strategy cannot fully utilize the minimum support constraint to prune the rowset search space. In this paper, we propose a new method called top-down mining together with a novel row enumeration tree to make full use of the pruning power of the minimum support constraint. Furthermore, to efficiently check if a rowset is closed, we develop a method called the trace-based method. Based on these methods, an algorithm called TD-Close is designed for mining a complete set of frequent closed patterns. To enhance its performance further, we improve it by using new pruning strategies and new data structures that lead to a new algorithm TTD-Close. Our performance study shows that the top-down strategy is effective in cutting down search space and saving memory space, while the trace-based method facilitates the closeness-checking. As a result, the algorithm TTD-Close outperforms the bottom-up search algorithms such as Carpenter and FPclose in most cases. It also runs faster than TD-Close.     

Efficient single-pass frequent pattern mining using a prefix-tree

The FP-growth algorithm using the FP-tree has been widely studied for frequent pattern mining because it can dramatically improve performance compared to the candidate generation-and-test paradigm of Apriori. However, it still requires two database scans, which are not consistent with efficient data stream processing. In this paper, we present a novel tree structure, called CP-tree (compact pattern tree), that captures database information with one scan (insertion phase) and provides the same mining performance as the FP-growth method (restructuring phase). The CP-tree introduces the concept of dynamic tree restructuring to produce a highly compact frequency-descending tree structure at runtime. An efficient tree restructuring method, called the branch sorting method, that restructures a prefix-tree branch-by-branch, is also proposed in this paper. Moreover, the CP-tree provides full functionality for interactive and incremental mining. Extensive experimental results show that the CP-tree is efficient for frequent pattern mining, interactive, and incremental mining with a single database scan.     

概念漂移数据流挖掘算法综述

数据流是一种新型的数据模型,具有动态、无限、高维、有序、高速和变化等特性。在真实的数据流环境中,一些数据分布是随着时间改变的,即具有概念漂移特征,称为可变数据流或概念漂移数据流。因此处理数据流模型的方法需要处理时空约束和自适应调整概念变化。对概念漂移问题和概念漂移数据流分类、聚类和模式挖掘等内容进行综述。首先介绍概念漂移的类型和常用概念改变检测方法。为了解决概念漂移问题,数据流挖掘中常使用滑动窗口模型对新近事务进行处理。数据流分类常用的模型包括单分类模型和集成分类模型,常用的方法包括决策树、分类关联规则等。数据流聚类方式通常包括基于k- means的和非基于k- means的。模式挖掘可以为分类、聚类和关联规则等提供有用信息。概念漂移数据流中的模式包括频繁模式、序列模式、episode、模式树、模式图和高效用模式等。最后详细介绍其中的频繁模式挖掘算法和高效用模式挖掘算法。     

频繁子图挖掘算法gSpan的设计与实现

由于大部分图挖掘算法都需要利用频繁子图,频繁子图挖掘逐渐成为了数据挖掘领域中的热点研究内容。目前,很多高效的频繁子图挖掘算法已经被提出。其中,gSpan算法是目前公认的最好的频繁子图挖掘算法。然而,在化合物数据集上,还可以利用化合物的特殊结构进一步优化gSpan算法的性能。文献利用了化合物分子结构的对称性和原子类型分布的不均衡性,提出了一些新的优化策略,进一步改进了gSpan的性能。鉴于gSpan算法在图挖掘领域乃至整个数据挖掘领域的重要性,设计并实现gSpan算法。同时,采用文献[4]中的优化策略,进一步提高gSpan算法在化合物数据集上的运行效率。     

一个高效的关联规则增量式更新算法

针对关联规则的维护问题,设计了一个高效的增量式更新算法ＦＩＵＡ,并将ＦＩＵＡ和已有的ＩＵＡ算法进行了比较,并通过实验证实了ＦＩＵＡ算法的高效性。     

基于动态交易项目集的关联规则更新

该文在交易数据库和最小支持度不变条件下,当用户动态地增加或删除交易项目集中的某些交易项目时,充分利用了交易项目集改变前已采掘出的频繁模式集,提出了两种关联规则的快速更新算法ｌｚｉ－ａｒ和Ｄｚｉ－ａｒ,经实验分析表明,该地关联规则的更 可行的和高效的。     

基于筛选压缩的类Apriori算法的研究

该文根据用户的Web访问路径应用关联规则和类Apriori算法挖掘出该用户的频繁访问路径,通过对Apriori算法和目前针对提高该算法效率的各种优化技术的详细分析和研究,对类Apriori算法进行了改进,提出了基于筛选压缩的类Apriori挖掘算法,并进行了模拟实验,比较结果显示基于筛选压缩的类Apriori挖掘算法挖掘用户频繁遍历路径的效率高于类Apriori算法,最终可获取用户的频繁遍历路径。